Computers have been used to implement and control displays of many types of images. In addition to displays of two-dimensional images (such as images of documents, graphs, spreadsheets and the like), it is sometimes desirable to provide a computer-controlled display which presents an image that has certain three-dimensional characteristics. One characteristic associated with three-dimensional scenes is a characteristic whereby, as an object is positioned or moved farther from the intended viewpoint of the viewer, the object appears to become smaller and subtends a smaller region of the overall scene. This characteristic will be referred to herein as "foreshortening." Another characteristic of three-dimensional displays is a characteristic wherein if two objects (or portions thereof) are collinear along a viewer's line of sight, only the closer object is fully visible, with some or all of the farther object along that line of sight being occluded and not visible. This property or characteristic will be referred to herein as "interposition" or "occlusion." Another characteristic of three-dimensional displays is a characteristic wherein a figure will appear to be dimmed in certain positions or environments, such as in the far distance or in fog, mist, or water. This property or characteristic will be referred to herein as "artifacting." Although the following description concentrates on foreshortening, occlusion and artifacting, there are also other characteristics of three-dimensional scenes such as parallax (the difference in appearance of a scene when viewed from the left eye or right eye) and depth queuing.
Some attempts to provide a display having certain three-dimensional characteristics have used fully three-dimensional calculations and/or rendering. For example, in some approaches, a three-dimensional space is modeled, assigning a picture element or pixel to each of a plurality of locations in the modeled three-dimensional space, i.e., pixels having height, width and depth (or X, Y, Z) values. The positions occupied by various objects are indicated by values assigned or associated with each of the three-dimnensional pixels typically stored in a computer memory as a three-dimensional array. FIG. 1 depicts a model of a three-dimensional space which is four pixels in width, three pixels in depth and nine pixels in height. Values may be stored, e.g. in a computer memory, to model such three-dimensional regions and objects. Manners of storing multi-dimensional arrays of data in memory are well-known to those of skill in the computing art. In some fully three-dimensional calculation methods, the three-dimensional objects are represented by one or more shells or polygons, e.g. by storing indications of the location and attitude of a plurality of faces of each modeled polygon. Returning to the example of FIG. 1, the two-dimensional display which will be projected on a display screen will depend upon the intended viewpoint of a user with respect to the modeled three-dimensional space. FIG. 1 depicts one viewpoint of the modeled three-dimensional region. However, if the viewpoint is selected to be that indicated at 12a of FIG. 1, the display will show the image as depicted in FIG. 2, while a viewpoint as indicated at 12b will result in a display showing the image as depicted in FIG. 3.
Various techniques have been used to convert stored three-dimensional mathematically modeled space into a two-dimensional view. In one technique, after selecting a viewpoint, a first two-dimensional image is formed corresponding to the objects which intersect a plane in the three-dimensional modeled space farthest from the viewpoint, followed by successively overdrawing the image with an image of objects (such as faces of polygons) located in planes successively closer to the viewpoint. Other methods of calculating a two-dimensional image to simulate a modeled three-dimensional space have also been used, such as ray-tracing methods. However, many of these methods for providing simulation of a three-dimensional space on a two dimensional display are believed to be computationally demanding and thus tend to execute very slowly unless performed on relatively large and sophisticated (and typically expensive) computers. In particular, some methods result in a computation load which is at least proportional to X.sup.3 where X is a measure of the size of the modeled three-dimensional region (such as a major diagonal).
Accordingly, it would be useful to provide a computer implementation for displaying a two-dimensional simulation of a three-dimensional region, preferably with the capability for user movement or manipulation of simulated objects in the three-dimensional region, and preferably including three-dimensional characteristics such as foreshortening, artifacting and/or occlusion while reducing or minimizing the required computations, thus making it feasible to use relatively low-cost computers for such simulation. Preferably the computation load is proportional to X.sup.n where n is less than about 3.